package combination;

public class Main {
	public static void main(String[] args) {
		//直接运行模板
		dfs(0,3);
		//重置vis
		vis = new boolean[20];
		//运行例子
		dfs_names(0,3);
	}

	//代码模板
	//记录每个下标位置，true表示放入组合，false表示不放入组合
	static boolean[] vis = new boolean[20];
	//dfs输出指定长度的组合
	//k:组合开始位置，给0即可
	//l:待组合元素的数量
	static void dfs(int k,int l){
		if(k==l) {
			//找到一个组合情况
			for(int i=0;i<l;i++) {
				if(vis[i])
					System.out.print(1);
				else
					System.out.print(0);
			}
			System.out.println();
			return;
		}
		else {
			vis[k] = false;      //选中当前元素
			dfs(k+1,l);          //选中当前元素进入后续dfs
			vis[k] = true;       //不选当前元素
			dfs(k+1,l);          //不选当前元素进入后续dfs
		}
	}
	
	//例：names的全部组合情况
	static String[] names = {"Tom","Mike","Lucy"};
	//模板稍作修改
	static void dfs_names(int k,int l){
		if(k==l) {
			//找到一个组合情况
			System.out.print("[");
			for(int i=0;i<l;i++) {
				if(vis[i])
					System.out.print(names[i]+" ");
			}
			System.out.println("]");
			return;
		}
		else {
			vis[k] = false;      //选中当前元素
			dfs_names(k+1,l);    //选中当前元素进入后续dfs
			vis[k] = true;       //不选当前元素
			dfs_names(k+1,l);    //不选当前元素进入后续dfs
		}
	}
}
